package leetcode.剑指offer.前40;

import org.ehcache.sizeof.SizeOf;
import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/23 9:22
 * @description :https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 */
public class 剑指_13_机器人的运动范围 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.movingCount(16, 8, 4));
    }


    class Solution {
        int[][] dirs = {{1, 0}, {0, 1}};
        public int movingCount(int m, int n, int k) {
            if (k == 0) return 1;
            boolean[][] isVisit = new boolean[m][n];
            Queue<int[]> queue = new LinkedList<>();
            int count = 1;
            isVisit[0][0] = true;
            queue.offer(new int[]{0, 0});
            while (!queue.isEmpty()) {
                int[] nums = queue.poll();
                int row = nums[0];
                int col = nums[1];
                for (int[] dir : dirs) {
                    int curRow = row + dir[0];
                    int curCol = col + dir[1];
                    if (curRow < 0 || curRow >= m || curCol < 0 || curCol >= n || isVisit[curRow][curCol] || sumXY(curRow, curCol) > k)
                        continue;
                    queue.offer(new int[]{curRow, curCol});
                    isVisit[curRow][curCol] = true;
                    count++;
                }
            }
            return count;
        }

        public int sumXY(int x, int y) {
            String str = x + "" + y;
            int sum = 0;
            for (char c : str.toCharArray()) {
                sum += c - '0';
            }
            return sum;
        }

    }


    /*
    class Solution {
        public int movingCount(int m, int n, int k) {
            if (k == 0) {
                return 1;
            }
            boolean[][] vis = new boolean[m][n];
            int ans = 1;
            vis[0][0] = true;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if ((i == 0 && j == 0) || get(i) + get(j) > k) {
                        continue;
                    }
                    // 边界判断
                    if (i - 1 >= 0) {
                        vis[i][j] |= vis[i - 1][j];
                    }
                    if (j - 1 >= 0) {
                        vis[i][j] |= vis[i][j - 1];
                    }
                    ans += vis[i][j] ? 1 : 0;
                }
            }
            return ans;
        }

        private int get(int x) {
            int res = 0;
            while (x != 0) {
                res += x % 10;
                x /= 10;
            }
            return res;
        }
    }
     */


}
